﻿#include <unordered_map>
#include "Operation.h"
#include "Vmtype.h"
#include "ServerInstance.h"
#include "ServerType.h"
#include "Parameter.h"
#include "Output.h"
#include "Input.h"
#include "strategy.h"
#include <cstdio>

using namespace std;
using namespace hw;

namespace hw {
    template<typename T>
    static vector<string> get_keys(const map<string,T>& data) {
        vector<string> res;
        for (auto i = data.cbegin(); i != data.cend() ; i++) {
            res.push_back(i->first);
        }
        return res;
    }
    int Strategy::_server_id = 0;

    //方法
    void Strategy::sort_server_type() {
        sorted_server_type = server_type;
        ::sort(sorted_server_type.begin(), sorted_server_type.end(), [](const ServerType &a, const ServerType &b) {
            double delta = a.m_c_ratio() - b.m_c_ratio();
            if (delta < 0) return true;
            if (delta > 0) return false;
            return a.hardware_price < b.hardware_price;
        });
    };

    void Strategy::migrate_single(ServerInstance *origin, ServerInstance *target, const std::string &vmid, Node node) {
        const Vmtype *vmtype = vm_dict[vmid].first;
        origin->free(*vmtype, vmid);
        target->allocate_appoint_node(*vmtype, vmid, node);
        vm_dict[vmid] = std::make_pair(vmtype, target);
    };

    ServerInstance *Strategy::find_server_for_vm_migrate(const Vmtype &vmtype, Node &node, int until) {
        //迁移时寻找最优的服务器
        auto c_threshold = parameter.migrate_c_threshold;
        auto m_threshold = parameter.migrate_m_threshold;
        auto signal_max_threshold = parameter.migrate_signal_max_threshold;
        auto double_max_threshold = parameter.migrate_double_max_threshold;
        ServerInstance *candidate = nullptr;
        if (server_list.empty()) {
            return nullptr;
        }
        //单双节点部署，选择最适合的情况
        if (vmtype.is_double) {
            node = Node::BOTH;
            ServerInstance* target = nullptr;
            int min_m = m_threshold;
            int min_c = c_threshold;
            for (int i = 0; i < until && i < server_list.size(); i++) {
                ServerInstance *server_instance = server_list[i];
                if (server_instance->can_fit(vmtype)) {
                    if (!candidate) candidate = server_instance;
                    auto double_remain_a_core = server_instance->a_core_remain - vmtype.core / 2;
                    auto double_remain_a_memory = server_instance->a_memory_remain - vmtype.memory / 2;
                    auto double_remain_b_core = server_instance->b_core_remain - vmtype.core / 2;
                    auto double_remain_b_memory = server_instance->b_memory_remain - vmtype.memory / 2;
                    if ((double_remain_a_memory < min_m && double_remain_a_core < min_c)
                        || (double_remain_b_memory < min_m && double_remain_b_core < min_c)){
                        node = Node::BOTH;
                        min_m = min(double_remain_b_memory, double_remain_a_memory);
                        min_c = min(double_remain_a_core, double_remain_b_core);
                        target = server_instance;
                    }
                }
            }
            if (target) return target;
            return candidate;
        } else {
            ServerInstance* target = nullptr;
            int min_m = m_threshold;
            int min_c = c_threshold;
            for (int i = 0; i < server_list.size() && i < until; i++) {
                ServerInstance *server_instance = server_list[i];
                if (server_instance->can_fit(vmtype)) {
                    if (candidate) {
                        if (server_instance->remain_core() < candidate->remain_core() && server_instance->remain_memory() < candidate->remain_memory())
                            candidate = server_instance;
                    } else {
                        candidate = server_instance;
                    }
                    auto single_remain_a_core = server_instance->a_core_remain - vmtype.core;
                    auto single_remain_a_memory = server_instance->a_memory_remain - vmtype.memory;
                    auto single_remain_b_core = server_instance->b_core_remain - vmtype.core;
                    auto single_remain_b_memory = server_instance->b_memory_remain - vmtype.memory;
                    if ((single_remain_a_memory <= min_m && single_remain_a_memory >= 0 &&
                         single_remain_a_core <= min_c && single_remain_a_core >= 0)) {
                        node = Node::A;
                        min_m = single_remain_a_memory;
                        min_c = single_remain_a_core;
                        target = server_instance;
                    }
                    if ((single_remain_b_memory <= min_m && single_remain_b_core <= min_c &&
                                single_remain_b_memory >= 0 && single_remain_b_core >= 0)){
                        node = Node::B;
                        min_m = single_remain_b_memory;
                        min_c = single_remain_b_core;
                        target = server_instance;
                    }
                }
            }
            if (target) return target;
            if (candidate) {
                if (candidate->can_fit_a(vmtype)) {
                    node = Node::A;
                } else {
                    node = Node::B;
                }
            }
            return candidate;
        }
        return nullptr;
    }

    void Strategy::migrate(vector<tuple<string, int, Node>> &res) {
        int attempted = 0, attempt_threshold = 2000, migrate_cnt = 0, start = 0, end = server_list.size() - 1;
        int migrate_threshold = vm_dict.size() * 3 / 100;
        while (start < end && migrate_cnt < migrate_threshold) {
            ServerInstance *origin = server_list[end];
            if (origin->a_memory_remain < 10 && origin->b_memory_remain < 10) {
                end--;
                continue;
            }
            vector<string> keys = get_keys(origin->record);

            for (const auto &vmid : keys) {
                const Vmtype *vmtype = vm_dict[vmid].first;
                //迁移一个虚拟机
                attempted++;
                Node node = Node::UNDEFINED;
                auto target = find_server_for_vm_migrate(*vmtype, node, end);
                if (target == origin) {
                    continue;
                }
                if (target) {
                    migrate_cnt++;
                    migrate_single(origin, target, vmid, node);
                    res.emplace_back(vmid, target->server_id, node);
                    break;
                }
                if (attempted > attempt_threshold || migrate_cnt >= migrate_threshold)
                    break;
            }
            end--;
            if (attempted > attempt_threshold || migrate_cnt >= migrate_threshold)
                break;

        }
    }

    void Strategy::migrate_single(ServerInstance *origin, ServerInstance *target, const string &vmid) {
        const Vmtype* vmtype = vm_dict[vmid].first;
        origin->free(*vmtype, vmid);
        target->allocate(*vmtype, vmid);
        vm_dict[vmid] = make_pair(vmtype, target);
    }

    void Strategy::migrate_one_pass(vector<tuple<string, int, Node>> &res) {
        // 一趟迁移，server_list右边空，左边满，从右往左迁
        int start = 0;
        int end = server_list.size()-1;
        int m_cnt = 0;
        int m = vm_dict.size() * 3 / 100;
        int fail_cnt = 0;
        int fail_m = 10;
        int attempt = 0;
        int attempt_m = 100000;
        if (end < 0) return;

        while (start < end && m_cnt < m && attempt < attempt_m) {
            ServerInstance* target = server_list[start];
            ServerInstance* origin = server_list[end];

            vector<string> keys = get_keys(origin->record);

            for (const auto& vmid : keys) {
                const Vmtype* vmtype = vm_dict[vmid].first;
                attempt ++;
                if (target->can_fit(*vmtype)) {
                    if (target == origin) continue;
                    this->migrate_single(origin, target, vmid);
                    res.emplace_back(vmid, target->server_id, target->record[vmid]);
                    fail_cnt = 0;
                    m_cnt ++;
                } else {
                    fail_cnt ++;
                }
                if (fail_cnt > fail_m) {
                    fail_cnt = 0;
                    end--;
                }
                if (end <= start || m >= m_cnt || attempt > attempt_m) break;

                target = server_list[start];
            }
            start++;
        }
    }

    void Strategy::migrate_fixed(vector<tuple<string,int,Node>>& res) {
        if (server_list.empty()) return;
        int len = server_list.size();
        int m_cnt = 0;
        int m_max = vm_dict.size() * 3 / 100;
        int attempt = 0;
        int attempt_max = 10000;

        int from_i = server_list.size()-1;
        int to_i = server_list.size() - len/2;
        for (int i = 0 ; i < len/2 ; i++) {
            ServerInstance* origin = server_list[from_i];
            ServerInstance* target = server_list[to_i];
            vector<string> keys = get_keys(origin->record);

            for (const auto& vmid : keys) {
                const Vmtype* vmtype = vm_dict[vmid].first;
                if (target->can_fit(*vmtype)) {
                    migrate_single(origin, target, vmid);
                    m_cnt ++;
                    res.emplace_back(vmid, target->server_id, target->record[vmid]);
                }
                if (m_cnt >= m_max) break;
            }
            if (m_cnt >= m_max) break;
            from_i--;
            to_i--;
        }

        from_i = len-1;
        to_i = 0;
        for (int i = 0 ; i < len/2 ; i++) {
            ServerInstance* origin = server_list[from_i];
            ServerInstance* target = server_list[to_i];

            vector<string> keys = get_keys(origin->record);

            for (const auto& vmid : keys) {
                const Vmtype* vmtype = vm_dict[vmid].first;
                if (target->can_fit(*vmtype)) {
                    migrate_single(origin, target, vmid);
                    m_cnt ++;
                    res.emplace_back(vmid, target->server_id, target->record[vmid]);
                }
                if (m_cnt >= m_max) break;
            }
            if (m_cnt >= m_max) break;
            from_i --;
            to_i ++;
        }

    }

    void Strategy::migrate_fixed_n(vector<tuple<string,int,Node>>& res, int n) {
        int m_cnt = 0;
        int m_h = vm_dict.size() * 3 / 100;

        for (int to_i = server_list.size()-1, end_i = max((int)server_list.size()-1-n,-1) ; to_i != end_i ; to_i--) {
            ServerInstance* target = server_list[to_i];

            for (int from_i = to_i - n; from_i >= 0 ; from_i -= n) {
                ServerInstance* origin = server_list[from_i];
                auto keys = get_keys(origin->record);
                for (const auto& vmid : keys) {
                    const Vmtype* vmtype = vm_dict[vmid].first;
                    if (target->can_fit(*vmtype)) {
                        migrate_single(origin, target, vmid);
                        m_cnt ++;
                        res.emplace_back(vmid, target->server_id, target->record[vmid]);
                    }
                    if (m_cnt >= m_h) break;
                }
                if (m_cnt >= m_h) break;
            }
            if (m_cnt >= m_h) break;
        }
    }

    void Strategy::migrate_half(vector<tuple<string,int,Node>>& res) {
        if (server_list.empty()) return;
        int len = server_list.size();
        int from_i = 0+len/2;
        int to_i = 0;
        int m_cnt = 0;
        int m_max = vm_dict.size() * 3 / 100;
        int attempt = 0;
        int attempt_max = 10000;

        for (; to_i < len/2 ; to_i++) {
            ServerInstance* target = server_list[to_i];
            for (int f_i = from_i ; f_i < len ; f_i++) {
                ServerInstance* origin = server_list[f_i];
                vector<string> keys = get_keys(origin->record);

                for (const auto& vmid : keys) {
                    const Vmtype* vmtype = vm_dict[vmid].first;
                    attempt++;
                    if (target->can_fit(*vmtype)) {
                        migrate_single(origin, target, vmid);
                        m_cnt ++;
                        res.emplace_back(vmid, target->server_id, target->record[vmid]);
                    }
                    if (m_cnt > m_max) break;
                    if (attempt >= attempt_max) break;
                }
                if (m_cnt > m_max) break;
                if (attempt >= attempt_max) break;
            }
            if (m_cnt > m_max) break;
            if (attempt >= attempt_max) break;
        }
    }

    static int partition(vector<pair<double,int>>& data, int lo, int hi) {
        int p = hi--;
        double pivot = data[p].first;
        while (lo <= hi) {
            while (lo <= hi && data[lo].first <= pivot) lo++;
            while (lo <= hi && data[hi].first > pivot) hi--;

            if (lo > hi) break;

            swap(data[lo], data[hi]);
        }
        swap(data[lo], data[p]);
        return lo;
    }

    static int quick_selection(vector<pair<double,int>>& data, int k) {
        if (data.size() <= k) return k;
        int lo = 0;
        int hi = data.size()-1;
        int t = -1;
        while (t != k) {
            t = partition(data, lo, hi);
            if (t < k) {
                lo = t+1;
            } else if (t > k) {
                hi = t-1;
            } else {
                return t;
            }
        }
        return t;
    }

    void Strategy::migrate_new(vector<tuple<string,int,Node>>& res) {
        int attempt = 0;
        int attempt_h = 40;
        int m_cnt = 0;
        int m_h = vm_dict.size() * 3 / 100;
        // 1. 统计占有率中位数
        vector<pair<double,int>> ratio;
        ratio.reserve(server_list.size());
        for (int i = 0 ; i < server_list.size() ; i++) ratio.emplace_back(1-server_list[i]->remain_ratio(), i);

        // 快速选择，找中位数
        int mid = ratio.size() / 2;
        quick_selection(ratio, mid);

        // 2. 把占有率低的服务器中的虚拟机往占有率高的服务器迁移
        for (int to_i = mid+1 ; to_i < ratio.size() ; to_i++) {
            ServerInstance* target = server_list[ratio[to_i].second];
            attempt = 0;
            for (int from_i = 0 ; from_i <= mid ; from_i++) {
                ServerInstance* origin = server_list[ratio[from_i].second];
                vector<string> keys = get_keys(origin->record);

                for (const auto& vmid : keys) {
                    const Vmtype* vmtype = vm_dict[vmid].first;
                    if (target->can_fit(*vmtype)) {
                        migrate_single(origin, target, vmid);
                        res.emplace_back(vmid, target->server_id, target->record[vmid]);
                        m_cnt++;
                        attempt = 0;
                    } else {
                        attempt++;
                    }
                    if (attempt > attempt_h) break;
                    if (m_cnt >= m_h) break;
                }
                if (attempt > attempt_h) break;
                if (m_cnt >= m_h) break;
            }
            if (m_cnt >= m_h) break;
        }
    }

    /*!
     * 按照服务器的占用率将服务器分为两部分，前k台的占用率大于后面所有服务器的占用率
     * @param k
     * @return
     */
    vector<pair<double,int>> Strategy::split_server_by_resource(int k) {
        vector<pair<double,int>> res;
        res.reserve(server_list.size());
        for (int i = 0 ; i < server_list.size() ; i++) res.emplace_back(server_list[i]->remain_ratio(), i);
        quick_selection(res, k);
        return res;
    }


    /*
     * 取较满的一部分server作为迁移target，其余作为origin
     * 将origin中的虚拟机按照大小排序（内存+core加权）
     */
    void Strategy::migrate_with_priority(vector<tuple<string,int,Node>>& res) {
        if (server_list.size() <= 1) return;

        int m_cnt = 0;
        int m_max = vm_dict.size() * 3 / 100;
        int target_len = server_list.size()/2;
        vector<pair<double,int>> ratio = split_server_by_resource(target_len);

        auto cal_resource = [](const Vmtype* vmtype) {
            return vmtype->memory * 0.5 + vmtype->core * 0.5;
        };

        // 对所有的origin虚拟机排序<虚拟机资源,虚拟机id>
        auto cmp = [](const tuple<double,string>& a, const tuple<double,string>& b){
            return std::get<0>(a) > std::get<0>(b);
        };

        priority_queue<tuple<double,string>,vector<tuple<double,string>>, decltype(cmp)> pq(cmp);

        for (int i = target_len ; i < ratio.size() ; i++) {
            ServerInstance* instance = server_list[ratio[i].second];
            for (auto it = instance->record.cbegin() ; it != instance->record.cend() ; it++) {
                const auto& vmid = it->first;
                pq.emplace(cal_resource(vm_dict[vmid].first), vmid);
            }
        }

        // 开始迁移
        int t_fail = 0;
        int t_max = 10;
        for (int i = 0 ; i < target_len ; i++) {
            ServerInstance* target = server_list[ratio[i].second];

            auto top = pq.top();
            auto& vmid = std::get<1>(top);
            auto d = vm_dict[vmid];
            while (!pq.empty() && target->can_fit(*d.first)) {
                ServerInstance* origin = d.second;
                migrate_single(origin, target, vmid);
                res.emplace_back(vmid, target->server_id, target->record[vmid]);
                pq.pop();
                if (pq.empty()) break;
                top = pq.top();
                d = vm_dict[std::get<1>(top)];
                t_fail = 0;
                if (++m_cnt >= m_max) break;
            }
            if (t_fail++ >= t_max) {
                if (!pq.empty()) pq.pop();
            }
            if (m_cnt >= m_max) break;
        }
    }

    /*
     * 疯狂地迁移，不管时间了
     */
    void Strategy::migrate_plain(vector<tuple<string,int,Node>>& res) {
        int m_cnt = 0;
        int m_h = vm_dict.size() * 3 / 100;

        for (int i = 0 ; i < server_list.size() ; i++) {
            ServerInstance* target = server_list[i];
            for (int j = server_list.size()-1 ; j > i ; j--) {
                ServerInstance* origin = server_list[j];
                auto keys = get_keys(origin->record);

                for (const auto& vmid : keys) {
                    const Vmtype* vmtype = vm_dict[vmid].first;
                    if (target->can_fit(*vmtype)) {
                        migrate_single(origin, target, vmid);
                        res.emplace_back(vmid, target->server_id, target->record[vmid]);
                        m_cnt ++;
                    }
                    if (m_cnt >= m_h) break;
                }
                if (m_cnt >= m_h) break;
            }
            if (m_cnt >= m_h) break;
        }
    }

    /*
     * 这是我最后的挣扎了, 如果这种迁移方法不能大幅降低成本，那就只能调参了
     * 按照单结点双结点对虚拟机分别排序
     */
    void Strategy::migrate_ultra_super_pro_max_plus(vector<tuple<string,int,Node>>& res, double d) {
        double ratio = d;
        int target_len = ratio * server_list.size();
        auto sorted = split_server_by_resource(target_len);

        int m_cnt = 0;
        int m_max = vm_dict.size() * 3 / 100;

        using entry = pair<const Vmtype*,string>;

        list<entry> single_vm;
        list<entry> double_vm;
        auto cal_resource = [](const Vmtype* vmtype) -> double {
            return vmtype->core * 0.5 + vmtype->memory * 0.5;
        };
        // 排序各个虚拟机
        for (int i = 0 ; i < server_list.size() ; i++) {
            ServerInstance* origin = server_list[sorted[i].second];
            for (auto it = origin->record.cbegin() ; it != origin->record.cend() ; it++) {
                const auto& vmid = it->first;
                const Vmtype* vmtype = vm_dict[vmid].first;
                if (vmtype->is_double) {
                    double_vm.emplace_back(vmtype, vmid);
                } else {
                    single_vm.emplace_back(vmtype, vmid);
                }
            }
        }
        auto cmp = [=](const entry& a, decltype(a) b) {
            return cal_resource(a.first) < cal_resource(b.first);
        };
        single_vm.sort(cmp);
        double_vm.sort(cmp);
        unordered_set<ServerInstance*> processed_server;

        // no time to tidy
        if (this->current_day == input->days * 2 / 3) {
            target_len = server_list.size();
            m_max = vm_dict.size();
            // 开始迁移
            for (int i = 0 ; i < target_len ; i++) {
                ServerInstance* target = server_list[sorted[i].second];

                // 找可以放到target中的vm
                // 找双结点的
                list<decltype(double_vm.end())> double_candidates;
                for (auto it = double_vm.begin() ; it != double_vm.end() ;) {
                    const Vmtype* vmtype = it->first;
                    if (target->can_fit(*vmtype)) {
                        double_candidates.push_back(it);
                        it ++;
                    } else {
                        it ++;
                    }
                    if (vmtype->core + vmtype->memory >= target->remain_core() + target->remain_memory()) break;
                    if (m_cnt >= m_max) break;
                }

                while (!double_candidates.empty()) {
                    auto i = double_candidates.back();
                    double_candidates.pop_back();

                    auto vmid = i->second;
                    const Vmtype* vmtype = i->first;
                    ServerInstance* origin = vm_dict[vmid].second;
                    if (processed_server.find(origin) != processed_server.end()) {
                        double_vm.erase(i);
                        continue;
                    }
                    if (target == origin) continue;

                    if (target->can_fit(*vmtype)) {
                        double_vm.erase(i);
                        migrate_single(origin, target, vmid);
                        res.emplace_back(vmid, target->server_id, target->record[vmid]);
                        m_cnt++;
                    }
                    if (m_cnt >= m_max) break;
                }
                if (m_cnt >= m_max) break;

                // 先找单结点的
                list<decltype(single_vm.end())> single_candidates;
                for (auto it = single_vm.begin() ; it != single_vm.end() ;) {
                    const Vmtype* vmtype = it->first;
                    if (target->can_fit(*vmtype)) {
                        single_candidates.push_back(it);
                        it ++;
                    } else {
                        it ++;
                    }
                    if (vmtype->core + vmtype->memory >= target->remain_core() + target->remain_memory()) break;

                }
                while (!single_candidates.empty()) {
                    auto i = single_candidates.back();
                    single_candidates.pop_back();

                    const Vmtype* vmtype = i->first;
                    auto vmid = i->second;
                    ServerInstance* origin = vm_dict[vmid].second;
                    if (processed_server.find(origin) != processed_server.end()) {
                        single_vm.erase(i);
                        continue;
                    }

                    if (target == origin) continue;

                    if (target->can_fit(*vmtype)) {
                        single_vm.erase(i);
                        migrate_single(origin, target, vmid);
                        res.emplace_back(vmid, target->server_id, target->record[vmid]);
                        m_cnt ++;
                    }
                    if (m_cnt >= m_max) break;
                }
                if (m_cnt >= m_max) break;

                processed_server.insert(target);
            }
            return;
        }
        // 开始迁移
        for (int i = 0 ; i < target_len ; i++) {
            ServerInstance* target = server_list[sorted[i].second];

            // 找可以放到target中的vm
            // 找双结点的
            list<decltype(double_vm.end())> double_candidates;
            for (auto it = double_vm.begin() ; it != double_vm.end() ;) {
                const Vmtype* vmtype = it->first;
                if (target->can_fit(*vmtype)) {
                    double_candidates.push_back(it);
                    it ++;
                } else {
                    it ++;
                }
                if (vmtype->core + vmtype->memory >= target->remain_core() + target->remain_memory()) break;
                if (m_cnt >= m_max) break;
            }

            while (!double_candidates.empty()) {
                auto i = double_candidates.back();
                double_candidates.pop_back();

                auto vmid = i->second;
                const Vmtype* vmtype = i->first;
                ServerInstance* origin = vm_dict[vmid].second;
                if (processed_server.find(origin) != processed_server.end()) {
                    double_vm.erase(i);
                    continue;
                }
                if (target == origin) continue;

                if (target->can_fit(*vmtype)) {
                    double_vm.erase(i);
                    migrate_single(origin, target, vmid);
                    res.emplace_back(vmid, target->server_id, target->record[vmid]);
                    m_cnt++;
                }
                if (m_cnt >= m_max) break;
            }
            if (m_cnt >= m_max) break;

            // 先找单结点的
            list<decltype(single_vm.end())> single_candidates;
            for (auto it = single_vm.begin() ; it != single_vm.end() ;) {
                const Vmtype* vmtype = it->first;
                if (target->can_fit(*vmtype)) {
                    single_candidates.push_back(it);
                    it ++;
                } else {
                    it ++;
                }
                if (vmtype->core + vmtype->memory >= target->remain_core() + target->remain_memory()) break;

            }
            while (!single_candidates.empty()) {
                auto i = single_candidates.back();
                single_candidates.pop_back();

                const Vmtype* vmtype = i->first;
                auto vmid = i->second;
                ServerInstance* origin = vm_dict[vmid].second;
                if (processed_server.find(origin) != processed_server.end()) {
                    single_vm.erase(i);
                    continue;
                }

                if (target == origin) continue;

                if (target->can_fit(*vmtype)) {
                    single_vm.erase(i);
                    migrate_single(origin, target, vmid);
                    res.emplace_back(vmid, target->server_id, target->record[vmid]);
                    m_cnt ++;
                }
                if (m_cnt >= m_max) break;
            }
            if (m_cnt >= m_max) break;

            processed_server.insert(target);
        }
        if (m_cnt >= m_max) return;

        // 在比较满的里面互相迁移
        // 先找一个中间服务器
        ServerInstance* single_mid = this->server_list[sorted.back().second];
        int max_core = single_mid->b_core_remain;
        int max_memory = single_mid->b_memory_remain;
        if (single_mid->a_core_remain >= max_core && single_mid->a_memory_remain >= max_memory) {
            max_core = single_mid->a_core_remain;
            max_memory = single_mid->a_memory_remain;
        }

        ServerInstance* double_mid = this->server_list[sorted.back().second];
        int d_max_core = double_mid->remain_double_core();
        int d_max_memory = double_mid->remain_double_memory();

        for (int i = target_len ; i < sorted.size() ; i++) {
            ServerInstance* inst = server_list[sorted[i].second];
            if (inst->remain_double_memory() >= d_max_memory && inst->remain_double_core() >= d_max_core) {
                double_mid = inst;
                d_max_core = inst->remain_double_core();
                d_max_memory = inst->remain_double_memory();
            }
            if (inst->a_core_remain >= max_core && inst->a_memory_remain >= max_memory) {
                max_core = inst->a_core_remain;
                max_memory = inst->a_memory_remain;
            }

            if (inst->b_core_remain >= max_core && inst->b_memory_remain >= max_memory) {
                max_core = inst->b_core_remain;
                max_memory = inst->b_memory_remain;
            }
        }

        for (int i = 0 ; i < target_len ; i++) {
            ServerInstance* instA = this->server_list[sorted[i].second];
            for (int j = target_len-1 ; j > i ; j--) {
                ServerInstance* instB = this->server_list[sorted[i].second];
                mutual_migrate(instA, instB, double_mid, single_mid, res);
            }
        }

        // 在不怎么满的里面互相迁移
    }

    void Strategy::mutual_migrate(ServerInstance* instA,
                                  ServerInstance* instB,
                                  ServerInstance* double_mid,
                                  ServerInstance* single_mid,
                                  vector<tuple<string,int,Node>>& res) {
        // 这个迁移方法的目的是把A填满，尽量平衡

        // 处理instA的A结点
        //if (instA->a_memory_remain)
    }

    void Strategy::reset_next_server_id() {
        Strategy::_server_id = 0;
    }

    int Strategy::next_server_id() {
        return Strategy::_server_id++;
    }

    void Strategy::run(Output *output) {
        this->result = output;
        // 读取前K-1天
        for (int i = 0; i < K - 1; i++) {
            read_next_day();
        }
        this->process();
    }

    void Strategy::process() {
        // 存储add操作的结果
        vector<pair<ServerInstance *, Node>> add_op_result;
        vector<tuple<string, int, Node>> migration_result;
        // 存储新买的服务器
        unordered_map<string, list<ServerInstance *>> new_instance;

        for (int dayi = 0; dayi < input->days; dayi++) {   // 处理一天的请求
            this->current_day = dayi;
            read_next_day();
            add_op_result.clear();
            new_instance.clear();
            migration_result.clear();
            day_memory = 0;
            day_core = 0;

            // 迁移
            if (input->days > 800) {
                migrate_ultra_super_pro_max_plus(migration_result, 0.9);
                //migrate_new(migration_result);
                //migrate_fixed(migration_result);
            } else {
                migrate_ultra_super_pro_max_plus(migration_result, 0.9);
                //migrate_fixed_n(migration_result, server_list.size()/8);
                //migrate_with_priority(migration_result);
                //migrate(migration_result);
                //migrate_new(migration_result);
            }
            /*
            if (server_list.size()*vm_dict.size() < 50000000L)
                migrate(migration_result);
            else
                migrate_ultra_super_pro_max_plus(migration_result);
                */
            //migrate(migration_result);
            //migrate_plain(migration_result);
            //migrate_ultra_super_pro_max_plus(migration_result);
            //migrate_fixed_n(migration_result, server_list.size()/32);
            //migrate_with_priority(migration_result);
            //migrate_new(migration_result);
            //migrate_fixed(migration_result);
            //migrate_one_pass(migration_result);
            //migrate_half(migration_result);
            /*
             * 在其余参数相同的情况下，按照性能排序
             * migrate
             * migrate_new      2007809714 5.85s
             * migrate_fixed    2013827613 3.62s
             * migrate_with_priority
             * migrate_one_pass 2085892566 2.35s
             * migrate_half     2091144920 3.44s
             * 其中migrate和migrate_new复杂度较高，其余较低
             */

            for (const auto &op : this->operation_list[dayi]) {
                if (op.mode == Op::ADD) {
                    bool created = false;
                    ServerInstance *inst = put_vm(op.vmid, vm_type_dict.at(op.vm_type_id), created);
                    if (created) {
                        auto &l = new_instance[inst->type.name];
                        l.push_back(inst);
                        server_list.push_back(inst);
                    }
                    Node n = inst->record[op.vmid];
                    add_op_result.emplace_back(inst, n);
                } else {
                    auto vm_a_inst = vm_dict[op.vmid];
                    vm_a_inst.second->free(*(vm_a_inst.first), op.vmid);
                    vm_dict.erase(op.vmid);
                    // pass
                }
            }

            /* 按照下面顺序输出一天的结果
             * 1. 购买
             * 2. 迁移
             * 3. 操作
             */

            result->start_purchase(new_instance.size());
            // 一天的请求处理完毕，给新买的服务器编号
            for (auto it = new_instance.begin(); it != new_instance.end(); it++) {
                if (it->second.empty()) continue;
                result->purchase_server(it->first, it->second.size());
                for (ServerInstance *inst : it->second) {
                    inst->server_id = next_server_id();
                }
            }

            result->start_migration(migration_result.size());
            for (const auto &tp : migration_result) {
                if (std::get<2>(tp) == Node::BOTH) {
                    // 双结点
                    result->migrate(std::get<0>(tp), std::get<1>(tp));
                } else {
                    result->migrate_single(std::get<0>(tp), std::get<1>(tp), std::get<2>(tp));
                }
            }

            // 输出一天的add请求结果
            for (const auto &p : add_op_result) {
                if (p.second == Node::BOTH) {
                    // 双结点
                    result->allocate(p.first->server_id);
                } else {
                    // 单结点
                    result->allocate_single(p.first->server_id, p.second);
                }
            }
            fflush(stdout);

            log("done processing day %d\n", dayi);
        }
        log("fallback: %d/%d\n", fallback_cnt, this->server_list.size());
        //printf("hit: %d\n", hit_cnt);
        //printf("total: %d\n", total);
        //printf("fallback: %d\n", fallback_cnt);
    }

    /*
     * 放置虚拟机
     */
    ServerInstance *Strategy::put_vm(const string &vmid, const Vmtype &vmtype, bool &created) {
        Node n;
        auto inst = find_server_for_vm(vmtype, n);
        if (!inst) {
            // 买一台
            inst = purchase_server_that_fit_vm(vmtype);
            created = true;
            inst->allocate(vmtype, vmid);
        } else {
            // 找到了，不用买
            inst->allocate_appoint_node(vmtype, vmid, n);
        }
        vm_dict[vmid] = make_pair(&vmtype, inst);
        if (vmid == "234696414") {
            int a = 0;
            a++;
        }

        look_ahead_core -= vmtype.core;
        look_ahead_memory -= vmtype.memory;
        used_memory_day += vmtype.memory;
        used_core_day += vmtype.core;
        return inst;
    }

    ServerInstance *Strategy::find_server_for_vm(const Vmtype &vmtype, Node &node) {
        auto c_threshold = parameter.put_c_threshold;
        auto m_threshold = parameter.put_m_threshold;
        auto signal_max_threshold = parameter.put_signal_max_threshold;
        auto double_max_threshold = parameter.put_double_max_threshold;

        ServerInstance *fallback_server = nullptr;

        if (vmtype.is_double) {
            total++;
            node = Node::BOTH;
            ServerInstance* target = nullptr;
            int min_m = m_threshold;
            int min_c = c_threshold;
            for (auto ri = server_list.begin(); ri != server_list.end(); ri++) {
                auto server_instance = (*ri);
                if (server_instance->can_fit(vmtype)) {
                    //if (!fallback_server) fallback_server = server_instance;
                    if (fallback_server) {
                        if (server_instance->remain_core() < fallback_server->remain_core() && server_instance->remain_memory() < fallback_server->remain_memory())
                            fallback_server = server_instance;
                    } else {
                        fallback_server = server_instance;
                    }
                    auto double_remain_a_core = server_instance->a_core_remain - vmtype.core / 2;
                    auto double_remain_a_memory = server_instance->a_memory_remain - vmtype.memory / 2;
                    auto double_remain_b_core = server_instance->b_core_remain - vmtype.core / 2;
                    auto double_remain_b_memory = server_instance->b_memory_remain - vmtype.memory / 2;
                    if ((double_remain_a_memory < min_m && double_remain_a_core < min_c)
                        || (double_remain_b_memory < min_m && double_remain_b_core < min_c)) {
                        min_m = min(double_remain_a_memory, double_remain_b_memory);
                        min_c = min(double_remain_a_core, double_remain_b_core);
                        //return server_instance;
                        target = server_instance;
                    }
                }
            }
            if (target) hit_cnt++;
            if (target) return target;
            if (fallback_server) {
                node = Node::BOTH;
                return fallback_server;
            }
        } else {
            ServerInstance* target = nullptr;
            int min_m = m_threshold;
            int min_c = c_threshold;
            for (auto ri = server_list.begin(); ri != server_list.end(); ri++) {
                auto server_instance = (*ri);
                if (server_instance->can_fit(vmtype)) {
                    if (!fallback_server) fallback_server = server_instance;
                    auto single_remain_a_core = server_instance->a_core_remain - vmtype.core;
                    auto single_remain_a_memory = server_instance->a_memory_remain - vmtype.memory;
                    auto single_remain_b_core = server_instance->b_core_remain - vmtype.core;
                    auto single_remain_b_memory = server_instance->b_memory_remain - vmtype.memory;
                    if ((single_remain_a_memory <= min_m && single_remain_a_memory >= 0 &&
                         single_remain_a_core <= min_c && single_remain_a_core >= 0)) {
                        node = Node::A;
                        min_m = single_remain_a_memory;
                        min_c = single_remain_a_core;
                        target = server_instance;
                        //return server_instance;
                    } else if ((single_remain_b_memory <= min_m && single_remain_b_core <= min_c &&
                                single_remain_b_memory >= 0 && single_remain_b_core >= 0)) {
                        node = Node::B;
                        min_m = single_remain_b_memory;
                        min_c = single_remain_b_core;
                        target = server_instance;
                        //return server_instance;
                    }
                }
            }
            if (target) {
                return target;
            }
            if (fallback_server) {
                if (fallback_server->can_fit_a(vmtype)) {
                    node = Node::A;
                } else if (fallback_server->can_fit_b(vmtype)) {
                    node = Node::B;
                } else {
                    log("fatal error in find_server_for_vm\n");
                    exit(-1);
                }
                return fallback_server;
            }
        }
        node = Node::UNDEFINED;
        return nullptr;
    }

    ServerInstance *Strategy::purchase_server_that_fit_vm(const Vmtype &vmtype) {
        /*
        int rest_m = this->look_ahead_memory;
        int rest_c = this->look_ahead_core;
         */
        double used_ratio = 0.66;
        double ahead_ratio = 1.0 - used_ratio;
        if (used_core_day == 0 || look_ahead_core == 0) return fallback_purchase(vmtype);
        double ratio_a = 1.0 * used_memory_day / used_core_day;
        double ratio_b = 1.0 * look_ahead_memory / look_ahead_core;
        //int rest_m = used_memory_day*used_ratio + this->look_ahead_memory*ahead_ratio;   // 往者可'鉴'，来者可追
        //int rest_c = used_core_day*used_ratio + this->look_ahead_core*ahead_ratio;

        //if (rest_c == 0) return fallback_purchase(vmtype);

        //double rest_ratio = 1.0 * rest_m / rest_c;
        double rest_ratio = ratio_a*used_ratio + ratio_b*ahead_ratio;
        double left_margin = parameter.leftmargin;
        double right_margin = parameter.rightmargin;
        auto ratio_range = make_pair(rest_ratio - left_margin, rest_ratio + right_margin);
        double delta = 1000000;
        int cost = 10000000;
        const ServerType *target_type = nullptr;
        const ServerType *target_type2 = nullptr;

        for (const auto & stype : sorted_server_type) {
            double r = stype.m_c_ratio();
            if (r >= ratio_range.first && r <= ratio_range.second) {
                if (stype.can_fit(vmtype)) {
                    if (stype.hardware_price < cost) {
                        cost = stype.hardware_price;
                        target_type = &stype;
                    }
                }
            }

            double d = abs(stype.m_c_ratio() - rest_ratio);
            if (d < delta) {
                delta = d;
                target_type2 = &stype;
            }
            if (r > ratio_range.second) break;
        }

        if (!target_type) {
            target_type = target_type2;
        }

        if (target_type) {
            if (target_type->can_fit(vmtype)) {
                return new ServerInstance(*target_type);
            }
        }
        // 没找到满足条件的，遍历所有类型
        return fallback_purchase(vmtype);
    }

    ServerInstance *Strategy::fallback_purchase(const Vmtype &vmtype) {
        fallback_cnt++;

        const ServerType* serverType = nullptr;
        for (auto it = server_type.begin(); it != server_type.end(); it++) {
            //for (const auto &stype : server_type) {
            auto &stype = (*it);
            //if (stype.can_fit(vmtype)) return new ServerInstance(stype);
            if (stype.can_fit(vmtype)) {
                if (serverType && stype.hardware_price < serverType->hardware_price)
                    serverType = &stype;
                else
                    serverType = &stype;
            }
        }
        return new ServerInstance(*serverType);
        // never reach here
        fprintf(stderr, "没有合适的服务器能购买\n");
        exit(-1);
    }

    Strategy::Strategy(Input *input, Parameter &parameter) : input(input), parameter(parameter), day_to_read(0),
                                                             current_day(0),
                                                             look_ahead_core(0), look_ahead_memory(0), used_core_day(0),
                                                             used_memory_day(0) {
        fallback_cnt = 0;
        hit_cnt = 0;
        total = 0;
        input->read_type_data(this->server_type, this->vm_type_dict);
        sort_server_type();
        this->K = input->K;
    }

    void Strategy::read_next_day() {
        if (this->operation_list.size() >= input->days) return;
        this->operation_list.push_back(input->read_next_day_operation());
        int core_sum = 0;
        int memory_sum = 0;
        for (const auto &op : this->operation_list[day_to_read]) {
            if (op.mode == Op::ADD) {
                auto &vmtype = vm_type_dict[op.vm_type_id];
                look_ahead_memory += vmtype.memory;
                look_ahead_core += vmtype.core;
                core_sum += vmtype.core;
                memory_sum += vmtype.memory;
            }
        }
        this->daily_resource.emplace_back(core_sum, memory_sum);
        day_to_read++;
    }


} // namespace hw

int
main(int argc, char **argv) {
    vector<vector<Operation>> operation_list;
    vector<ServerType> server_type;
    unordered_map<string, Vmtype> vm_type;
    vector<pair<int, int>> daily_resource;
    //ifstream in("../../../data2/training-1.txt");
    Input input(cin);
    //Data::read_data_z_edition(cin, operation_list, vm_type, server_type, daily_resource);

    if (argc >= 10) {
        Parameter parameter(
                atoi(argv[1]),
                atoi(argv[2]),
                atoi(argv[3]),
                atoi(argv[4]),
                atoi(argv[5]),
                atoi(argv[6]),
                atoi(argv[7]),
                atoi(argv[8]),
                atof(argv[9]),
                atof(argv[10])
        );
        Output result(stdout);
        Strategy strategy(&input, parameter);
        strategy.run(&result);
    } else {
        //Parameter parameter(10, 6, 55, 34, 8, 14, 88, 76, 0.1, 0.175);
        Parameter parameter(4, 14, 42, 20, 8, 24, 105, 42, 0.17, 0.5);
        //Parameter parameter(5, 10, 36, 17, 7, 15, 105, 32, 0.1, 0.195);
        Output result(stdout);
        Strategy strategy(&input, parameter);
        strategy.run(&result);
    }


    return 0;
}
